package Solutions

func largestSumOfAverages(nums []int, k int) float64 {
	var cache = make([][]float64, len(nums))
	preSum := make([]int, len(nums)+1)
	preSum[0] = 0
	for i := 0; i < len(nums); i++ {
		preSum[i+1] = preSum[i] + nums[i]
	}
	for i := range nums {
		cache[i] = make([]float64, k+1)
	}
	var minAver func(int, int) float64
	minAver = func(l int, divide int) float64 {
		if cache[l][divide] != 0 {
			return cache[l][divide]
		}
		if divide == 1 {
			cache[l][1] = float64(preSum[len(preSum)-1]-preSum[l]) / float64((len(nums) - l))
			return cache[l][1]
		}
		maxScore := float64(0)
		for i := l + 1; i < len(nums); i++ {
			avg := float64(preSum[i]-preSum[l])/float64(i-l) + minAver(i, divide-1)
			if avg > maxScore {
				maxScore = avg
			}
		}
		cache[l][divide] = maxScore
		return maxScore

	}
	minAver(0, k)
	return cache[0][k]
}